//
// Created by yanhai on 2021/1/4.
//

// 归并排序 - 非递归版本
// 思想：分而治之，把整体的每一个元素当成最小的组
//      然后再把这些小的组一点点有序的归并起来，最后归并成一个完整的有序的集合
// 自下而上排序归并

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

// 核心代码：将（data中的）start到middle和middle+1到end的两个有序集合合并为一个start到end的有序集合（存放在temp中）
// 和上一个例子中的_sort不同，这里最后不需要再将temp里面的数据拷贝会data中
// 注意：middle是包含在第1组里面的
void _sort(const int *data, int *temp, int start, int middle, int end)
{
    int i = start, j = middle + 1, k = start;
    while (i <= middle && j <= end) {
        // 这里应该加上等号
        // 假如data[i]==data[j]，如果不加等号，那么就会把data[j]放到前面，造成排序是不稳定的
        if (data[i] <= data[j]) {
            temp[k++] = data[i++];
        } else {
            temp[k++] = data[j++];
        }
    }
    // 将剩下的追加到temp后面
    while (i <= middle) {
        temp[k++] = data[i++];
    }
    while (j <= end) {
        temp[k++] = data[j++];
    }
    // 再把临时数据拷贝到data中，这里不再需要拷贝，
    // 如果是像上一篇那样，使用递归的方式，就需要拷贝回去，
    // 因为递归当中，每次使用的源数据都是在data中的，
    // 做不到像这样，数据一会在data中，一会在temp中。
//    for (i = start; i <= end; i++) {
//        data[i] = temp[i];
//    }
}

// 核心代码
// 将src中相邻的长度为gap的子序列两两归并到dst中
void _merge_pass(int *src, int *dst, int gap, int length)
{
    int i = 0;
    int j;

    // length - 2*gap， 2gap就是2组的长度， length-2*gap出来就是恰好剩余是2组长度的时的下标。
    // 如果i大于这个下标，就表示从i开始到最后已经没有2组的长度了，
    // 有可能剩1组多点，也有可能剩下的不到1组。退出循环。
    while (i <= length - 2 * gap) {
        _sort(src, dst, i, i + gap - 1, i + 2 * gap - 1); // 两两归并 ([i, i+gap-1] 是第1组，[i+gap, i+2*gap-1]是第2组)
        i += 2 * gap;    // 向后跳2个子序列长度
    }
    // 如果i后面剩下的超过1组，但是不到2组的长度，说明还有2个子序列，只是第2个子序列比第1个要短而已，
    // 我们依然要合并这2个子序列
    // 这里就不需要=号，因为如果等于就表示恰好剩余的长度是1个组的长度，那也就不需要合并，直接拷贝进来就行了
    // 因为单个子序列本身就是有序的
    if (i < length - gap) {
        _sort(src, dst, i, i + gap - 1, length - 1);
    } else {
        // 剩下的就是1个有序的子序列
        for (j = i; j < length; j++) {
            dst[j] = src[j];
        }
    }
}

// 对data中的数据进行归并排序
void _merge_sort(int *data, int *temp, int length)
{
    int k = 1;  // 每个组的长度，也可以称为组距。默认情况下，每个元素自己就是一个组，这样就确保每个组都是有序的

    // 每组的间距还没有到达整个数组的长度，说明还有多组，还需要继续归并
    while (k < length) {
        // 这次归并，把数据从data中归并到temp中
        _merge_pass(data, temp, k, length);
        k *= 2;     // 经过上面的归并，子序列长度加倍

        // 这次归并，再把temp中的数据归并到data中，他们两个依次的交换过来交换过去
        // 这样做的好处是，不用每次使用完temp，就立即把temp里面的数据再拷贝回来，减少拷贝次数
        // 有可能会出现这样的情况：就是上面一次归并结束后，就已经只剩下一个组了，那么整个数组就已经是有序的了
        // 那么执行下面的代码，就仅仅是从temp把数据拷贝到data中来而已。
        _merge_pass(temp, data, k, length);
        k *= 2;     // 经过上面的归并，子序列长度加倍
    }
}

// 这个函数仅仅就是对_merge_sort函数包装一下，申请了临时空间而已。
// 由于只申请了一块和元数据长度一样的内存空间，因此空间复杂度是O(n)
// 时间复杂度为 O(nlogn)
// 并且避免递归也在时间性能上有一定的提示，
// 应该说，使用归并排序时，尽量考虑用非递归方法。
int merge_sort(int *data, int length)
{
    // 准备临时空间
    int *temp = (int *) malloc(length * sizeof(int));
    if (temp == NULL) {
        return 1;
    }
    _merge_sort(data, temp, length);
    free(temp);
    return 0;
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {71, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    merge_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
